class Solution:
    """这个还有点问题"""
    def characterReplacement(self, s: str, k: int) -> int:
        return max(self.search(s, k), self.search(s[::-1], k))

    def search(self, s, k):
        if not s:
            return 0
        length, res = len(s), 0
        for index, alpha in enumerate(s):
            mid = k
            for i in range(index + 1, length):
                if s[i] != alpha:
                    if mid:
                        mid -= 1
                    else:
                        res = max(res, i - index)
                        break
            else:
                res = max(res, length - index)
                break
        return res


from collections import defaultdict


class Solution2:
    def characterReplacement(self, s: str, k: int) -> int:
        num_dic = defaultdict(int)
        right, max_num, res = -1, 0, 0
        length = len(s)
        for left in range(length):
            while True:
                right += 1
                if right >= length:
                    break
                num_dic[s[right]] += 1
                max_num = max(max_num, num_dic[s[right]])
                if right - left + 1 > k + max_num:
                    break
            res = max(res, right - left)
            num_dic[s[left]] -= 1
            max_num = max(max_num, num_dic[s[left]])
            left += 1
        return res


a = Solution2()
print(a.characterReplacement(s="ABAB", k=2))  # 4
print(a.characterReplacement(s="AABABBA", k=1))  # 4
print(a.characterReplacement("ABBB", 2))  # 4
print(a.characterReplacement("ABBBA", 2))  # 5
